package leetcode_周赛._2023._12;

import java.util.Arrays;

/**
 * 第 374 场周赛
 * AC_1
 *
 * @author yezh
 * @date 2023/12/3 21:49
 */
public class _03 {

    /**
     * 2952.需要添加的硬币的最小数量
     * 算法: 贪心
     * 时间复杂度: (nlogn + log target)
     * 用归纳法思考
     * 得到了 [0, s - 1] 区间内的所有整数, 加入一个 x, 就会得到 [x, s + x - 1] 内的所有整数
     * x <= s 时, 新区间为 [s, s + s - 1], 可以和旧区间合并
     * x > s 时, 新区间不能和旧区间合并, 此时需要再加数字, 否则, 就不能得到整数 s
     * 区间为啥要从 0 开始, 为了好做一点, 因为 [0, 0] 肯定存在
     */
    public int minimumAddedCoins(int[] coins, int target) {
        // 目前有 [0, s - 1] 的所有整数
        int ans = 0, n = coins.length, s = 1, i = 0;
        Arrays.sort(coins);
        // s - 1 >= target 即 s > target 时结束循环
        while (s <= target) {
            if (i < n && coins[i] <= s) {
                // 小于 s, 可以合并
                s += coins[i];
                i++;
            } else {
                // 大于 s, 不可以合并, 需要添加一个 s
                ++ans;
                // s - 1 + s = 2s - 1  <=> s * 2 - 1
                s *= 2;
            }
        }
        return ans;
    }

}
